package graph.weighted.minimun_spanning_tree;

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Queue;

import graph.weighted.CandyWeightedEdge;
import graph.weighted.CandyWeightedGraph;
import graph.weighted.connectedComponent.CandyConnectedComponent;
/**
 * 
 * @Title: CandyPrim.java 
 * @Package graph.weighted.minimun_spanning_tree 
 * @Description: 求解最小生成树：prim算法
 *                  1、基于v1改进，每次循环不用遍历所有的边，只需要考虑 跟 当前已经纳入最小生成树的那些顶点相邻的边即可，
 *                    每次循环后纳入最小生成树中的顶点数会增加，只需将新加入的顶点的相邻的顶点加入到优先队列中
 * @author CandyWall   
 * @date 2021年1月20日 下午4:22:27 
 * @version V1.0
 */
public class CandyPrim_v2 {
    private CandyWeightedGraph graph; 
    
    public CandyPrim_v2(CandyWeightedGraph graph) {
        this.graph = graph;
    }
    
    /**
     * 获取最小生成树中的所有边
     * @return
     */
    public ArrayList<CandyWeightedEdge> getMst() {
        ArrayList<CandyWeightedEdge> mst = new ArrayList<>();
        CandyConnectedComponent connectedComponent = new CandyConnectedComponent(graph);
        if(connectedComponent.getConnectedComponentCount() > 1) {
            return mst;
        }
        
        // Prim
        boolean[] visited = new boolean[graph.getVertex_num()];
        // 先把顶点0纳入生成树中
        visited[0] = true;
        Queue<CandyWeightedEdge> queue = new PriorityQueue<>();
        // 将跟顶点0相连的横切边添加到优先队列中
        for(int w : graph.adjacentVertexes(0)) {
            queue.add(new CandyWeightedEdge(0, w, graph.getWeight(0, w)));
        }
        // 队列为空，说明已经从队列中取出了n-1条最短横切边，也表示所有的顶点都已经纳入到了最小生成树中。
        while(!queue.isEmpty()) {
            // 取出1条最短横切边
            CandyWeightedEdge minEdge = queue.remove();
            // 获取这条边的两个顶点
            int v = minEdge.getV();
            int w = minEdge.getW();
            // 如果两个顶点中有任意一个没有被纳入最小生成数的顶点中，表示该边是目前最短的横切边，是最小生成树的边
            if(!visited[v] || !visited[w]) {
                // 记录该边
                mst.add(minEdge);
                // 切分扩张，将新的点加入到切分点中
                int newV = visited[v] ? w : v;
                visited[newV] = true;
                // 将新纳入最小生成树的点相邻的没有遍历过的边加入到优先队列中
                for(int u : graph.adjacentVertexes(newV)) {
                    if(!visited[u]) {
                        queue.add(new CandyWeightedEdge(newV, u, graph.getWeight(newV, u)));
                    }
                }
            }
        }
        return mst;
    }

    public static void main(String[] args) {
        CandyWeightedGraph graph = new CandyWeightedGraph("testData/weightedGraph/graph.txt");
        CandyPrim_v2 prim = new CandyPrim_v2(graph);
        System.out.println(prim.getMst());
    }
}
